/*@Describe:一个js没有的数据结构的定义与操作模块
 *@Author:李志
 *@Time：2019-05-10
 */
define(function() {
	/* 栈 后进先出（LIFO）原则的有序集合 
	1.push(element(s))：添加一个（或几个）新元素到栈顶;
	2.pop()：移除栈顶的元素，同时返回被移除的元素;
	3.peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）;
	4.isEmpty()：如果栈里没有任何元素就返回true，否则返回false;
	5.clear()：移除栈里的所有元素;
	6.size()：返回栈里的元素个数。这个方法和数组的length属性很类似。*/
	function Stack() {
		//各种属性和方法的声明
		var items = []; //创建栈数组
		this.push = function(element) {
			items.push(element);
		};
		this.pop = function() {
			return items.pop();
		};
		this.peek = function() {
			return items[items.length - 1];
		};
		this.isEmpty = function() {
			return items.length == 0;
		};
		this.size = function() {
			return items.length;
		};
		this.clear = function() {
			items = [];
		};
	}
	/* 队列 遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项
	1.enqueue(element(s))：向队列尾部添加一个（或多个）新的项；
	2.dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素;
	3.front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不
	做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似;
	4.isEmpty()：如果队列中不包含任何元素，返回true，否则返回false;
	5.size()：返回队列包含的元素个数，与数组的length属性类似。
	 */
	function Queue() {
		//这里是属性和方法
		var items = []; //现Queue类和Stack类非常类似，只是添加和移除元素的原则不同
		this.enqueue = function(element) {
			items.push(element);
		};
		this.dequeue = function() {
			return items.shift();
		};
		this.front = function() {
			return items[0];
		};
		this.isEmpty = function() {
			return items.length == 0;
		}
		this.size = function() {
			return items.length;
		};
		this.print = function() {
			console.log(items.toString());
		};
	};

	//优先队列
	//实现优先队列的两种方式：
	//1.设置优先级，然后在正确的位置添加元素；
	//2.用入列操作添加元素，然后按照优先级移除它们。
	//1
	function PriorityQueue() {
		var items = [];

		function QueueElement(element, priority) { // {1} 
			this.element = element;
			this.priority = priority;
		}
		this.enqueue = function(element, priority) {
			var queueElement = new QueueElement(element, priority);
			if (items.length == 0) {
				items.push(queueElement); // {2} 
			} else {
				var added = false;
				for (var i = 0; i < items.length; i++) {
					if (queueElement.priority < items[i].priority) {
						items.splice(i, 0, queueElement); // {3} 
						added = true;
						break; // {4}
					}
				}
				if (!added) { //{5} 
					items.push(queueElement);
				}
			}
		};
		//其他方法和默认的Queue实现相同
		this.dequeue = function() {
			return items.shift();
		};
		this.front = function() {
			return items[0];
		};
		this.isEmpty = function() {
			return items.length == 0;
		}
		this.size = function() {
			return items.length;
		};
		this.print = function() {
			console.log(JSON.stringify(items));
		};
	};
	/* 链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个
	 * 元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。
	 * append(element)：向列表尾部添加一个新的项；
	 * insert(position, element)：向列表的特定位置插入一个新的项；
	 * remove(element)：从列表中移除一项；
	 * indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1；
	 * removeAt(position)：从列表的特定位置移除一项；
	 * isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false；
	 * size()：返回链表包含的元素个数。与数组的length属性类似；
	 * toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
	 */
	function LinkedList() {
		var Node = function(element) { // {1} 
			this.element = element;
			this.next = null;
		};
		var length = 0; // {2} 
		var head = null; // {3} 
		this.append = function(element) {
			var node = new Node(element), //{1} 
				current; //{2} 
			if (head === null) { //列表中第一个节点 //{3} 
				head = node;
			} else {
				current = head; //{4} 
				//循环列表，直到找到最后一项
				while (current.next) {
					current = current.next;
				}
				//找到最后一项，将其next赋为node，建立链接
				current.next = node; //{5} 
			}
			length++; //更新列表的长度 //{6} 
		};
		this.insert = function(position, element) {
			//检查越界值
			if (position >= 0 && position <= length) { //{1} 
				var node = new Node(element),
					current = head,
					previous,
					index = 0;
				if (position === 0) { //在第一个位置添加
					node.next = current; //{2} 
					head = node;
				} else {
					while (index++ < position) { //{3} 
						previous = current;
						current = current.next;
					}
					node.next = current; //{4} 
					previous.next = node; //{5} 
				}
				length++; //更新列表的长度
				return true;
			} else {
				return false; //{6} 
			}
		};
		this.removeAt = function(position) {
			//检查越界值
			if (position > -1 && position < length) { // {1} 
				var current = head, // {2} 
					previous, // {3} 
					index = 0; // {4} 
				//移除第一项
				if (position === 0) { // {5} 
					head = current.next;
				} else {
					while (index++ < position) { // {6} 
						previous = current; // {7} 
						current = current.next; // {8} 
					}
					//将previous与current的下一项链接起来：跳过current，从而移除它
					previous.next = current.next; // {9} 
				}
				length--; // {10} 
				return current.element;
			} else {
				return null; // {11} 
			}
		};
		this.toString = function() {
			var current = head, //{1} 
				string = ''; //{2} 
			while (current) { //{3} 
				string += current.element + ","; //{4} 
				current = current.next; //{5} 
			}
			return string.substring(0, string.length - 1); //{6} 
		};
		this.indexOf = function(element) {
			var current = head, //{1} 
				index = -1;
			while (current) { //{2} 
				if (element === current.element) {
					return index; //{3} 
				}
				index++; //{4} 
				current = current.next; //{5} 
			}
			return -1;
		};
		this.remove = function(element) {
			var index = this.indexOf(element);
			return this.removeAt(index);
		};
		this.isEmpty = function() {
			return length === 0;
		};
		this.size = function() {
			return length;
		};
		this.getHead = function() {
			return head;
		};
	};
	/* 双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，
	 * 而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。
	 */
	function DoublyLinkedList() {
		var Node = function(element) {
			this.element = element;
			this.next = null;
			this.prev = null; //新增的
		};
		var length = 0;
		var head = null;
		var tail = null; //新增的
		//这里是方法
		this.append = function(element) {
			var node = new Node(element), //{1} 
				current; //{2} 
			if (head === null) { //列表中第一个节点 //{3} 
				head = node;
			} else {
				current = head; //{4} 
				//循环列表，直到找到最后一项
				while (current.next) {
					current = current.next;
				}
				//找到最后一项，将其next赋为node，建立链接
				current.next = node; //{5} 
			}
			length++; //更新列表的长度 //{6} 
		};
		this.insert = function(position, element) {
			//检查越界值
			if (position >= 0 && position <= length) {
				var node = new Node(element),
					current = head,
					previous,
					index = 0;
				if (position === 0) { //在第一个位置添加
					if (!head) { //新增的 {1} 
						head = node;
						tail = node;
					} else {
						node.next = current;
						current.prev = node; //新增的 {2} 
						head = node;
					}
				} else if (position === length) { //最后一项 //新增的
					current = tail; // {3} 
					current.next = node;
					node.prev = current;
					tail = node;
				} else {
					while (index++ < position) { //{4} 
						previous = current;
						current = current.next;
					}
					node.next = current; //{5} 
					previous.next = node;
					current.prev = node; //新增的
					node.prev = previous; //新增的
				}
				length++; //更新列表的长度
				return true;
			} else {
				return false;
			}
		};
		this.removeAt = function(position) {
			//检查越界值
			if (position > -1 && position < length) {
				var current = head,
					previous,
					index = 0;
				//移除第一项
				if (position === 0) {
					head = current.next; // {1} 
					//如果只有一项，更新tail //新增的
					if (length === 1) { // {2} 
						tail = null;
					} else {
						head.prev = null; // {3} 
					}
				} else if (position === length - 1) { //最后一项 //新增的
					current = tail; // {4} 
					tail = current.prev;
					tail.next = null;
				} else {
					while (index++ < position) { // {5} 
						previous = current;
						current = current.next;
					}
					//将previous与current的下一项链接起来——跳过current 
					previous.next = current.next; // {6} 
					current.next.prev = previous; //新增的
				}
				length--;
				return current.element;
			} else {
				return null;
			}
		};
		this.toString = function() {
			var current = head, //{1} 
				string = ''; //{2} 
			while (current) { //{3} 
				string += current.element + ","; //{4} 
				current = current.next; //{5} 
			}
			return string.substring(0, string.length - 1); //{6} 
		};
	};
	/* 集合是由一组无序且唯一（即不能重复）的项组成的。
	 * 1.add(value)：向集合添加一个新的项。
	 * 2.remove(value)：从集合移除一个值。
	 * 3.has(value)：如果值在集合中，返回true，否则返回false。
	 * 4.clear()：移除集合中的所有项。
	 * 5.size()：返回集合所包含元素的数量。与数组的length属性类似。
	 * 6.values()：返回一个包含集合中所有值的数组。
	 * 7.A∪B = { x | x ∈ A∨x ∈ B } union() 并集
	 * 8.A∩B = { x | x ∈ A∧x ∈ B } intersection() 交集
	 * 9.A-B = { x | x ∈ A ∧ x B } difference() 差集
	 * 10.∀x { x ∈ A → x ∈ B } subset() 子集
	 */
	function Set() {
		var items = {};
		this.has = function(value) {
			return items.hasOwnProperty(value);
		};
		this.add = function(value) {
			if (!this.has(value)) {
				items[value] = value; //{1} 
				return true;
			}
			return false;
		};
		this.remove = function(value) {
			if (this.has(value)) {
				delete items[value]; //{2} 
				return true;
			}
			return false;
		};
		this.clear = function() {
			items = {}; // {3} 
		};
		this.size = function() {
			var count = 0;
			for (var prop in items) { //{5} 
				if (items.hasOwnProperty(prop)) //{6} 
					++count; //{7} 
			}
			return count;
		};
		this.values = function() {
			var keys = [];
			for (var key in items) { //{7} 
				keys.push(key); //{8} 
			}
			return keys;
		};
		this.union = function(otherSet) {
			var unionSet = new Set(); //{1} 
			var values = this.values(); //{2} 
			for (var i = 0; i < values.length; i++) {
				unionSet.add(values[i]);
			}
			values = otherSet.values(); //{3} 
			for (var i = 0; i < values.length; i++) {
				unionSet.add(values[i]);
			}
			return unionSet;
		};
		this.intersection = function(otherSet) {
			var intersectionSet = new Set(); //{1} 
			var values = this.values();
			for (var i = 0; i < values.length; i++) { //{2} 
				if (otherSet.has(values[i])) { //{3} 
					intersectionSet.add(values[i]); //{4} 
				}
			}
			return intersectionSet;
		};
		this.difference = function(otherSet) {
			var differenceSet = new Set(); //{1} 
			var values = this.values();
			for (var i = 0; i < values.length; i++) { //{2} 
				if (!otherSet.has(values[i])) { //{3}
					differenceSet.add(values[i]); //{4} 
				}
			}
			return differenceSet;
		};
		this.subset = function(otherSet) {
			if (this.size() > otherSet.size()) { //{1} 
				return false;
			} else {
				var values = this.values();
				for (var i = 0; i < values.length; i++) { //{2} 
					if (!otherSet.has(values[i])) { //{3} 
						return false; //{4} 
					}
				}
				return true; //{5} 
			}
		};
	};
	/* 字典则是以[键，值]的形式来存储元素。字典也称作映射。 
	 * 1.set(key,value)：向字典中添加新元素。
	 * 2.remove(key)：通过使用键值来从字典中移除键值对应的数据值。
	 * 3.has(key)：如果某个键值存在于这个字典中，则返回true，反之则返回false。
	 * 4.get(key)：通过键值查找特定的数值并返回。
	 * 5.clear()：将这个字典中的所有元素全部删除。
	 * 6.size()：返回字典所包含元素的数量。与数组的length属性类似。
	 * 7.keys()：将字典所包含的所有键名以数组形式返回。
	 * 8.values()：将字典所包含的所有数值以数组形式返回。
	 */
	function Dictionary() {
		var items = {};
		this.has = function(key) {
			return key in items;
		};
		this.set = function(key, value) {
			items[key] = value; //{1} 
		};
		this.remove = function(key) {
			if (this.has(key)) {
				delete items[key];
				return true;
			}
			return false;
		};
		this.get = function(key) {
			return this.has(key) ? items[key] : undefined;
		};
		this.values = function() {
			var values = [];
			for (var k in items) { //{1} 
				if (this.has(k)) {
					values.push(items[k]); //{2} 
				}
			}
			return values;
		};
		this.clear = function() {
			items = {}; // {3} 
		};
		this.size = function() {
			var count = 0;
			for (var prop in items) { //{5} 
				if (items.hasOwnProperty(prop)) //{6} 
					++count; //{7} 
			}
			return count;
		};
		this.keys = function() {
			var keys = [];
			for (var key in items) { //{7} 
				keys.push(key); //{8} 
			}
			return keys;
		};
		this.getItems = function() {
			return items;
		}
	};
	/* 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构 。
	 * 1.put(key,value)：向散列表增加一个新的项（也能更新散列表）。
	 * 2.remove(key)：根据键值从散列表中移除值。
	 * 3.get(key)：返回根据键值检索到的特定的值。
	 */
	function HashTable() {
		var table = [];
		var djb2HashCode = function(key) {
			var hash = 5381; //{1} 
			for (var i = 0; i < key.length; i++) { //{2} 
				hash = hash * 33 + key.charCodeAt(i); //{3} 
			}
			return hash % 1013; //{4} 
		};
		this.put = function(key, value) {
			var position = djb2HashCode(key); //{5} 
			console.log(position + ' - ' + key); //{6} 
			table[position] = value; //{7} 
		};
		this.get = function(key) {
			return table[djb2HashCode(key)];
		};
		this.remove = function(key) {
			table[djb2HashCode(key)] = undefined;
		};
	};
	/* 二叉搜索树（BST）只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。 
	 * 1.insert(key)：向树中插入一个新的键。
	 * 2.search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false。
	 * 3.inOrderTraverse：通过中序遍历方式遍历所有节点。
	 * 4.preOrderTraverse：通过先序遍历方式遍历所有节点。
	 * 5.postOrderTraverse：通过后序遍历方式遍历所有节点。
	 * 6.min：返回树中最小的值/键。
	 * 7.max：返回树中最大的值/键。
	 * 8.remove(key)：从树中移除某个键。
	 */
	function BinarySearchTree() {
		var Node = function(key) { //{1} 
			this.key = key;
			this.left = null;
			this.right = null;
		};
		var root = null; //{2} 
		this.insert = function(key) {
			var newNode = new Node(key); //{1} 
			if (root === null) { //{2} 
				root = newNode;
			} else {
				insertNode(root, newNode); //{3} 
			}
		};
		var insertNode = function(node, newNode) {
			if (newNode.key < node.key) { //{4} 
				if (node.left === null) { //{5} 
					node.left = newNode; //{6} 
				} else {
					insertNode(node.left, newNode); //{7} 
				}
			} else {
				if (node.right === null) { //{8} 
					node.right = newNode; //{9} 
				} else {
					insertNode(node.right, newNode); //{10}
				}
			};
			this.inOrderTraverse = function(callback) {
				inOrderTraverseNode(root, callback); //{1} 
			};
			var inOrderTraverseNode = function(node, callback) {
				if (node !== null) { //{2} 
					inOrderTraverseNode(node.left, callback); //{3} 
					callback(node.key); //{4} 
					inOrderTraverseNode(node.right, callback); //{5} 
				}
			};
			this.preOrderTraverse = function(callback) {
				preOrderTraverseNode(root, callback);
			};
			var preOrderTraverseNode = function(node, callback) {
				if (node !== null) {
					callback(node.key); //{1} 
					preOrderTraverseNode(node.left, callback); //{2} 
					preOrderTraverseNode(node.right, callback); //{3} 
				}
			};
			this.postOrderTraverse = function(callback) {
				postOrderTraverseNode(root, callback);
			};
			var postOrderTraverseNode = function(node, callback) {
				if (node !== null) {
					postOrderTraverseNode(node.left, callback); //{1} 
					postOrderTraverseNode(node.right, callback); //{2} 
					callback(node.key); //{3} 
				}
			};
			this.min = function() {
				return minNode(root); //{1} 
			};
			var minNode = function(node) {
				if (node) {
					while (node && node.left !== null) { //{2} 
						node = node.left; //{3} 
					}
					return node.key;
				}
				return null; //{4} 
			};
			this.max = function() {
				return maxNode(root);
			};
			var maxNode = function(node) {
				if (node) {
					while (node && node.right !== null) { //{5} 
						node = node.right;
					}
					return node.key;
				}
				return null;
			};
			this.search = function(key) {
				return searchNode(root, key); //{1} 
			};
			var searchNode = function(node, key) {
				if (node === null) { //{2} 
					return false;
				}
				if (key < node.key) { //{3} 
					return searchNode(node.left, key); //{4} 
				} else if (key > node.key) { //{5} 
					return searchNode(node.right, key); //{6} 
				} else {
					return true; //{7} 
				}
			};
			this.remove = function(key) {
				root = removeNode(root, key); //{1} 
			};
			var removeNode = function(node, key) {
				if (node === null) { //{2} 
					return null;
				}
				if (key < node.key) { //{3} 
					node.left = removeNode(node.left, key); //{4} 
					return node; //{5} 
				} else if (key > node.key) { //{6} 
					node.right = removeNode(node.right, key); //{7} 
					return node; //{8} 
				} else { //键等于node.key 
					//第一种情况——一个叶节点
					if (node.left === null && node.right === null) { //{9} 
						node = null; //{10} 
						return node; //{11} 
					}
					//第二种情况——一个只有一个子节点的节点
					if (node.left === null) { //{12} 
						node = node.right; //{13} 
						return node; //{14} 
					} else if (node.right === null) { //{15} 
						node = node.left; //{16} 
						return node; //{17} 
					}
					//第三种情况——一个有两个子节点的节点
					var aux = findMinNode(node.right); //{18} 
					node.key = aux.key; //{19} 
					node.right = removeNode(node.right, aux.key); //{20} 
					return node; //{21} 
				}
			};
		};
	}
	/* 图是网络结构的抽象模型。图是一组由边连接的节点（或顶点）。任何二元关系都可以用图来表示。
	 *
	 */
	function Graph() {
		var vertices = []; //{1} 
		var adjList = new Dictionary(); //{2} 
		this.addVertex = function(v) {
			vertices.push(v); //{3} 
			adjList.set(v, []); //{4} 
		};
		this.addEdge = function(v, w) {
			adjList.get(v).push(w); //{5}
			adjList.get(w).push(v); //{6} 
		};
		this.toString = function() {
			var s = '';
			for (var i = 0; i < vertices.length; i++) { //{10} 
				s += vertices[i] + ' -> ';
				var neighbors = adjList.get(vertices[i]); //{11} 
				for (var j = 0; j < neighbors.length; j++) { //{12} 
					s += neighbors[j] + ' ';
				}
				s += '\n'; //{13} 
			}
			return s;
		};
		var initializeColor = function() {
			var color = [];
			for (var i = 0; i < vertices.length; i++) {
				color[vertices[i]] = 'white'; //{1} 
			}
			return color;
		};
		//广度优先搜索
		this.bfs = function(v, callback) {
			var color = initializeColor(), //{2} 
				queue = new Queue(); //{3} 
			queue.enqueue(v); //{4} 
			while (!queue.isEmpty()) { //{5} 
				var u = queue.dequeue(), //{6} 
					neighbors = adjList.get(u); //{7}
				color[u] = 'grey'; // {8} 
				for (var i = 0; i < neighbors.length; i++) { // {9} 
					var w = neighbors[i]; // {10} 
					if (color[w] === 'white') { // {11} 
						color[w] = 'grey'; // {12} 
						queue.enqueue(w); // {13} 
					}
				}
				color[u] = 'black'; // {14} 
				if (callback) { // {15} 
					callback(u);
				}
			}
		};
		this.BFS = function(v) {
			var color = initializeColor(),
				queue = new Queue(),
				d = [], //{1} 
				pred = []; //{2} 
			queue.enqueue(v);
			for (var i = 0; i < vertices.length; i++) { //{3} 
				d[vertices[i]] = 0; //{4} 
				pred[vertices[i]] = null; //{5}
			}
			while (!queue.isEmpty()) {
				var u = queue.dequeue(),
					neighbors = adjList.get(u);
				color[u] = 'grey';
				for (i = 0; i < neighbors.length; i++) {
					var w = neighbors[i];
					if (color[w] === 'white') {
						color[w] = 'grey';
						d[w] = d[u] + 1; //{6} 
						pred[w] = u; //{7} 
						queue.enqueue(w);
					}
				}
				color[u] = 'black';
			}
			return { //{8} 
				distances: d,
				predecessors: pred
			};
		};
		//深度优先搜索
		this.dfs = function(callback) {
			var color = initializeColor(); //{1}
			for (var i = 0; i < vertices.length; i++) { //{2} 
				if (color[vertices[i]] === 'white') { //{3} 
					dfsVisit(vertices[i], color, callback); //{4} 
				}
			}
		};
		var dfsVisit = function(u, color, callback) {
			color[u] = 'grey'; //{5} 
			if (callback) { //{6} 
				callback(u);
			}
			var neighbors = adjList.get(u); //{7} 
			for (var i = 0; i < neighbors.length; i++) { //{8} 
				var w = neighbors[i]; //{9} 
				if (color[w] === 'white') { //{10} 
					dfsVisit(w, color, callback); //{11} 
				}
			}
			color[u] = 'black'; //{12} 
		};
		var time = 0; //{1} 
		this.DFS = function() {
			var color = initializeColor(), //{2} 
				d = [],
				f = [],
				p = [];
			time = 0;
			for (var i = 0; i < vertices.length; i++) { //{3} 
				f[vertices[i]] = 0;
				d[vertices[i]] = 0;
				p[vertices[i]] = null;
			}
			for (i = 0; i < vertices.length; i++) {
				if (color[vertices[i]] === 'white') {
					DFSVisit(vertices[i], color, d, f, p);
				}
			}
			return { //{4} 
				discovery: d,
				finished: f,
				predecessors: p
			};
		};
		var DFSVisit = function(u, color, d, f, p) {
			console.log('discovered ' + u);
			color[u] = 'grey';
			d[u] = ++time; //{5} 
			var neighbors = adjList.get(u);
			for (var i = 0; i < neighbors.length; i++) {
				var w = neighbors[i];
				if (color[w] === 'white') {
					p[w] = u; // {6} 
					DFSVisit(w, color, d, f, p);
				}
			}
			color[u] = 'black';
			f[u] = ++time; //{7} 
			console.log('explored ' + u);
		};
	};
	//排序算法
	function ArrayList() {
		var array = []; //{1} 
		this.insert = function(item) { //{2} 
			array.push(item);
		};
		this.toString = function() { //{3} 
			return array.join();
		};
		//冒泡算法
		this.bubbleSort = function() {
			var length = array.length; //{1} 
			for (var i = 0; i < length; i++) { //{2} 
				for (var j = 0; j < length - 1; j++) { //{3} 
					if (array[j] > array[j + 1]) { //{4} 
						swap(j, j + 1); //{5} 
					}
				}
			}
		};
		// 改进后的冒泡算法
		this.modifiedBubbleSort = function() {
			var length = array.length;
			for (var i = 0; i < length; i++) {
				for (var j = 0; j < length - 1 - i; j++) { //{1} 
					if (array[j] > array[j + 1]) {
						swap(j, j + 1);
					}
				}
			}
		};
		// 选择排序
		this.selectionSort = function() {
			var length = array.length, //{1} 
				indexMin;
			for (var i = 0; i < length - 1; i++) { //{2} 
				indexMin = i; //{3} 
				for (var j = i; j < length; j++) { //{4} 
					if (array[indexMin] > array[j]) { //{5} 
						indexMin = j; //{6} 
					}
				}
				if (i !== indexMin) { //{7} 
					swap(i, indexMin);
				}
			}
		};
		//插入排序
		this.insertionSort = function() {
			var length = array.length, //{1} 
				j, temp;
			for (var i = 1; i < length; i++) { //{2} 
				j = i; //{3} 
				temp = array[i]; //{4} 
				while (j > 0 && array[j - 1] > temp) { //{5} 
					array[j] = array[j - 1]; //{6} 
					j--;
				}
				array[j] = temp; //{7} 
			}
		};
		//归并排序
		this.mergeSort = function() {
			array = mergeSortRec(array);
		};
		var mergeSortRec = function(array) {
			var length = array.length;
			if (length === 1) { //{1} 
				return array; //{2} 
			}
			var mid = Math.floor(length / 2), //{3} 
				left = array.slice(0, mid), //{4} 
				right = array.slice(mid, length); //{5} 
			return merge(mergeSortRec(left), mergeSortRec(right)); //{6} 
		};
		var merge = function(left, right) {
			var result = [], // {7} 
				il = 0,
				ir = 0;
			while (il < left.length && ir < right.length) { // {8} 
				if (left[il] < right[ir]) {
					result.push(left[il++]); // {9} 
				} else {
					result.push(right[ir++]); // {10} 
				}
			}
			while (il < left.length) { // {11} 
				result.push(left[il++]);
			}
			while (ir < right.length) { // {12} 
				result.push(right[ir++]);
			}
			return result; // {13} 
		};
		//快速排序
		this.quickSort = function() {
			quick(array, 0, array.length - 1);
		};
		var quick = function(array, left, right) {
			var index; //{1} 
			if (array.length > 1) { //{2} 
				index = partition(array, left, right); //{3} 
				if (left < index - 1) { //{4} 
					quick(array, left, index - 1); //{5} 
				}
				if (index < right) { //{6} 
					quick(array, index, right); //{7} 
				}
			}
		};
		var partition = function(array, left, right) {
			var pivot = array[Math.floor((right + left) / 2)], //{8} 
				i = left, //{9} 
				j = right; //{10} 
			while (i <= j) { //{11} 
				while (array[i] < pivot) { //{12} 
					i++;
				}
				while (array[j] > pivot) { //{13} 
					j--;
				}
				if (i <= j) { //{14} 
					swapQuickStort(array, i, j); //{15} 
					i++;
					j--;
				}
			}
			return i; //{16} 
		};
		var swapQuickStort = function(array, index1, index2) {
			var aux = array[index1];
			array[index1] = array[index2];
			array[index2] = aux;
		};
	}
	return {
		Stack: Stack,
		Queue: Queue,
		PriorityQueue: PriorityQueue,
		LinkedList: LinkedList,
		DoublyLinkedList: DoublyLinkedList,
		Set: Set,
		Dictionary: Dictionary,
		HashTable: HashTable,
		BinarySearchTree: BinarySearchTree,
		Graph: Graph
	}

});
